// https://www.lintcode.com/problem/min-deletions-to-obtain-string-in-right-format/

public class Solution {
    /**
     * @param s: the string
     * @return: Min Deletions To Obtain String in Right Format
     */
    public int minDeletionsToObtainStringInRightFormat(String s) {
        // write your code here
        int ret = s.length();
        int numsA = 0, numsB = 0;
        int[][] baCount = new int[s.length()][];
        for (int i = 0; i < s.length(); ++i) {
            baCount[i] = new int[]{numsB, 0};
            if (s.charAt(i) == 'B') {
                ++numsB;
            }
        }
        for (int i = s.length() - 1; i > -1; --i) {
            baCount[i][1] = numsA;
            if (s.charAt(i) == 'A') {
                ++numsA;
            }
        }
        for (int i = 0; i < s.length(); ++i) {
            int chars = baCount[i][0] + baCount[i][1];
            if (chars < ret) {
                ret = chars;
            }
        }
        return ret;
    }
}